The Rationale behind Paxos Design Choices
Understand the rationale behind Paxos protocol design choices and how they help achieve consensus on a single value.
We'll cover the following
We learned how the basic Paxos algorithm works with many examples. This lesson revisits many Paxos rules and explores the rationale behind those decisions.
The three roles#
This design choice is very intuitive. Let’s continue with the example of deciding on a food place for Lunch. Some members need to propose some suggestions; otherwise, we would not have any options to consider. The members who give suggestions can be called proposers. Because we need to choose one place from the total list of suggestions, there should be some mechanism that can help us decide. One way to do that is through voting. Then, we need voters that can vote against the proposed suggestions. We’ll call these members of the group the acceptors.
We should also consider a situation where some of the members are not available or have no issue with whatever the final decision is. They just learn the final decision and are happy with that. Also, all the available members of the group need to learn the final chosen value. We call these members of the group the learners.
Here, we might think that the final chosen value would be the one that got the maximum number of votes. But would that work? Let's see in the following section.
Getting majority votes#
We saw in the previous lesson how in the Paxos protocol, a value is chosen only if it gets majority votes. We might wonder why we need a majority (more than half of the total number of votes) when instead we can just choose the value with the highest number of votes. Let's state the difference between having the highest number of votes and having majority votes in the following way to understand why Paxos needs to get majority votes to choose a value.
- The highest number of votes: Let’s consider that there are a total of 6 members of the group. Three members voted for proposal 1, two voted for proposal 2, and the remaining one voted for proposal 3. Here, the proposal that got the highest number of votes is proposal 1. None of the proposals got majority votes because the majority consists of more than half of the total group members, which is 4 out of 6 in this example.
- Majority votes: Consider the same situation, that there are a total of 6 members of the group. Four members voted for proposal 1, while two voted for proposal 2. Here, the proposal that got majority votes is proposal 1.
Note: The majority comprises more than half of the total members of the group. In real systems, the total number of the group is usually an odd number so we can’t have an even split of votes.
What could be the problem with getting the highest number of votes to choose the final value? This approach can result in a tie. Multiple proposals can get the same number of votes. And in such a situation, we cannot choose a single value. To avoid this issue, we use the majority votes approach.
Obtaining a majority of votes facilitates the selection of a single value because any two majorities share at least one acceptor. This is applicable if an acceptor can only accept one value; that’s why we have a value selection condition in the Paxos protocol that needs to be followed by the proposers while sending an accept request. This condition guarantees that an acceptor will accept at most one value.
Note: Taking majority votes enables us to stick with a decision once a decision has been made.
Point to ponder
Question
Why don’t we designate a single acceptor responsible for choosing the first proposed value that it receives?
This is an easy solution to choose a value, but it is unreliable. The failure of the single acceptor makes it impossible to make progress and choose the value.
A single acceptor’s failure probability is higher than that of a majority set of acceptors.
The two-step protocol#
Why does the Paxos protocol consist of two phases? Can't we reach a consensus in a single step (requesting the majority to accept a value)?
We will start with the contradiction, assuming that the proposers are directly proposing the value and requesting the acceptors accept that value. And we will then examine the need that led to adding a prepare phase before the accept phase. Here, acceptors will follow the rule of accepting the first proposal they see and then never changing it.
1 of 9
2 of 9
3 of 9
4 of 9
5 of 9
6 of 9
7 of 9
8 of 9
9 of 9
Suppose we let the acceptors change their decision by allowing them to accept the latest request and discard the old one. In that case, multiple proposals (every new proposal) can get the majority on a proposed value of their own choice and choose that value. This leads to multiple and different values being chosen after a value has already been chosen. This also violates the safety property.
So knowing about the proposals already in motion before proposing a new proposal with a new value is a must for safety as well as liveness. Therefore, there is a two-phase protocol where the proposers discover the already accepted proposal in the first phase and then wisely propose the value from the values already in motion. This helps choose a single value. The safety property can not be violated this way. This protocol is shown in the following illustration:
1 of 15
2 of 15
3 of 15
4 of 15
5 of 15
6 of 15
7 of 15
8 of 15
9 of 15
10 of 15
11 of 15
12 of 15
13 of 15
14 of 15
15 of 15
Rules followed by the acceptors#
As we saw in the previous lesson, the following rules need to be followed by the acceptors. They are easy to understand and intuitive.
Accepting at least one proposal: It ensures that a value can be chosen where we have only one proposal. Therefore, the acceptors should always accept the first proposal they receive. If we don't make it necessary, that can lead to a situation where no value is chosen.
Promising a proposal with a higher proposal number: It ensures that we include every new proposal in the final decision.
Rules followed by the proposers#
The proposers send their proposals according to the rules below:
A new proposal can be proposed with a large number: It helps us because we do not keep track of every proposal; we just need to remember the latest proposal.
Value selection condition at the proposers: It ensures the safety property by choosing a single value. The proposer first finds out the values already accepted by the acceptors in the majority quorum, then chooses the value with the highest proposal number and proposes that value.
Liveness with the distinguished proposer#
A distinguished proposer helps make progress and eventually chooses a value (the goal of the Paxos). It works under the assumption that a good part (more than half) of the system—which includes the proposer, acceptors, and communication network—is operating correctly.
We simulated the Paxos protocol using the distinguished proposer in the previous lesson. However, that was the ideal situation when the whole system was working correctly, and there was no failure. We will now simulate the protocol in the presence of some failures and see different scenarios.
No progress scenario#
A majority set of acceptors should be available at any time. This is the assumption by which the Paxos protocol works. Still, we can get into a situation when we can’t make progress even if the majority set of acceptors is available; this occurs when we have a different list of acceptors in the majority set at different times. The majority set of acceptors that was available at the time of prepare request was not the same at the time of the accept request. And more precisely, if we have the acceptors fail and recover in the same pattern repeatedly, then we can’t make progress.
For example, if the acceptors {A, B} from the majority set of available acceptors promised to a prepare request on proposal ID “k” and one of the acceptors (for example, B) failed when an accept request for proposal "k" was sent to the acceptors that promised on “k” earlier, then we wouldn't be able to get majority acceptance for proposal “k” and the corresponding value in the request, despite having a new majority set of acceptor {A, C} at that time.
The proposer will try again with another proposal number. If the above same situation happens again and again with each new proposal, we won't reach a consensus. This is shown in the following illustration:
Note: The next two slide decks are very similar to the ones we saw earlier about the dueling proposers problem and the distinguished proposer solution.
1 of 23
2 of 23
3 of 23
4 of 23
5 of 23
6 of 23
7 of 23
8 of 23
9 of 23
10 of 23
11 of 23
12 of 23
13 of 23
14 of 23
15 of 23
16 of 23
17 of 23
18 of 23
19 of 23
20 of 23
21 of 23
22 of 23
23 of 23
Progress under the assumption of the same majority set#
Progress can only be made and a value can only be chosen when we have the same set of majority acceptors remaining available at the time of prepare requests as well as the following accept requests for at least one of the proposals, as shown in the following illustration.
1 of 26
2 of 26
3 of 26
4 of 26
5 of 26
6 of 26
7 of 26
8 of 26
9 of 26
10 of 26
11 of 26
12 of 26
13 of 26
14 of 26
15 of 26
16 of 26
17 of 26
18 of 26
19 of 26
20 of 26
21 of 26
22 of 26
23 of 26
24 of 26
25 of 26
26 of 26
Handling node failures in majority quorum#
Paxos tolerates the failures of less than half of the total nodes in the cluster. If a proposer gets its proposal promised by a majority of the acceptors, it sends an accept request with a proposed value. If a proposer gets its proposed value accepted by a majority of the acceptors (the majority quorum), then that value is chosen, and no other value is chosen afterward. The protocol execution during partial failures is shown below:
1 of 6
2 of 6
3 of 6
4 of 6
5 of 6
6 of 6
In this lesson, we learned about the basic Paxos protocol and the rationale behind the algorithm decision. In the next lesson, we will learn about multi-Paxos, an extension of the basic Paxos algorithm.
Basic Paxos in Action
Multi-Paxos